package leetcode.code0081;

public class Solution extends Solution81 {
	@Override
	public boolean search(int[] nums, int target) {
		int len = nums.length;
		int l = 0;
		int r = len - 1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			int L = nums[l];
			int R = nums[r];
			int M = nums[m];
			if (M == target || L == target || R == target) {
				return true;
			} else if (L == R) {
				l++;
				r--;
			} else if (L > M) {// 大头落在L和M之间了，L~M没有单调性，M~R之间单调
				if (target > M && target < R) {// target落在单调区间
					l = m + 1;
				} else {// 不在单调区间就到不单调区间找
					r = m - 1;
				}
			} else {// L< M 大头落在M和R之间了， M~R之间没有单调性，L~M之间有单调性
				if (target > L && target < M) {
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
//		so.debug5();
//		so.debug6();
		so.debug7();

	}

}
